package leetcode.每日一题;

import com.sun.jmx.remote.internal.ArrayQueue;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/11 10:26
 * @description：https://leetcode-cn.com/problems/escape-a-large-maze/
 */
public class 逃离大迷宫 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {
        // 在包围圈中
        static final int BLOCKED = -1;
        // 不在包围圈
        static final int VALID = 0;
        // target和source在一起
        static final int FOUND = 1;

        final int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        static final int BOUNDARY = 1000000;

        public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
            if (blocked.length < 2) return true;
            Set<Pair> blockedSet = new HashSet<>();
            for (int[] nums : blocked) {
                blockedSet.add(new Pair(nums[0], nums[1]));
            }
            int res = check(blocked, source, target, blockedSet);
            if (res == FOUND) return true;
            if (res == BLOCKED) return false;
            return check(blocked, target, source, blockedSet) != BLOCKED;
        }

        private int check(int[][] blocked, int[] source, int[] target, Set<Pair> blockedSet) {
            int sx = source[0], sy = source[1];
            int tx = target[0], ty = target[1];
            int n = blocked.length;
            int countdown = n * (n - 1) / 2;
            Pair sN = new Pair(sx, sy);
            Queue<Pair> queue = new ArrayDeque<>();
            queue.offer(sN);
            Set<Pair> visited = new HashSet<>();
            visited.add(sN);
            while (!queue.isEmpty() && countdown > 0) {
                Pair cur = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int curx = cur.x + dirs[i][0];
                    int cury = cur.y + dirs[i][1];
                    Pair curN = new Pair(curx, cury);
                    if (curx >= 0 && curx < BOUNDARY
                            && cury >= 0 && cury < BOUNDARY
                            && !blockedSet.contains(curN)
                            && !visited.contains(curN)) {
                        if (curx == tx && cury == ty) {
                            return FOUND;
                        }
                        countdown--;
                        queue.offer(curN);
                        visited.add(curN);
                    }
                }
            }
            if (countdown > 0) return BLOCKED;
            return VALID;
        }
    }
    class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return x == pair.x &&
                    y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

}
